P4035 [JSOI2008]球形空间产生器

设原形坐标为 OO,圆上一点坐标为 AA

由提示得:

r=i=1n(AiOi)2r=\sqrt{\sum_{i=1}^n(A_i-O_i)^2}

r2=i=1n(AiOi)2r^2=\sum_{i=1}^n(A_i-O_i)^2

r2=i=1nAi2+Oi22AiOir^2=\sum_{i=1}^n{A_i^2+O_i^2-2A_iO_i}

r2i=1nOi22AiOi=i=1nAi2r^2-\sum_{i=1}^nO_i^2-2A_iO_i=\sum_{i=1}^n{A_i^2}

i=1n2AiOi+(r2i=1nOi2)=i=1nAi2\sum_{i=1}^n2A_iO_i+(r^2-\sum_{i=1}^nO_i^2)=\sum_{i=1}^n{A_i^2}

括号內的式子与 AA 无关,可单独看作一个变量。

因为有 n+1n+1 个点,就有 n+1n+1AiA_i ,列出 n+1n+1 个方程消元即可。

我不会告诉你因为我这题SA打挂了才用的这种方法。

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define eps 1e-12

const int MAXN = 10;
int n;
double a[ MAXN + 5 ][ MAXN + 5 ];

void Gauss( ) {
    for( int i = 1 ; i <= n ; i ++ ) {
        int pos = i;
        for( int j = i + 1 ; j <= n ; j ++ )
            if( fabs( a[ j ][ i ] ) > fabs( a[ pos ][ i ] ) ) pos = j;
        swap( a[ pos ] , a[ i ] );
        for( int j = 1 ; j <= n ; j ++ )
            if( i != j ) {
                double t = a[ j ][ i ] / a[ i ][ i ];
                for( int k = i ; k <= n + 1 ; k ++ )
                    a[ j ][ k ] -= t * a[ i ][ k ];
            } 
    }
}

int main( ) {
    scanf("%d",&n); n ++;
    double A;
    for( int i = 1 ; i <= n ; i ++ ) {
    	for( int j = 1 ; j <= n - 1 ; j ++ )
            scanf("%lf",&A) , a[ i ][ j ] = 2 * A , a[ i ][ n + 1 ] += A * A;
        a[ i ][ n ] = 1;
	}
    Gauss( );
    for( int i = 1 ; i <= n - 1 ; i ++ ) printf("%.3f ", a[ i ][ n + 1 ] / a[ i ][ i ] );
    return 0;
}